home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / seqdemos / hamming.icl < prev    next >
Text File  |  1992-08-07  |  2KB  |  64 lines
  1. MODULE hamming;
  2.  
  3. <<
  4. The Hamming Function.
  5.  
  6. The result of this program is a list of the first NrElements numbers
  7. having only 2, 3 and 5 as prime factors. Result:
  8.  
  9.     [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,...].
  10. >>
  11.  
  12. IMPORT deltaI;
  13.  
  14.  
  15. MACRO
  16.  
  17.     NrElements -> 300;  == The number of Hamming numbers to be calculated.
  18.  
  19.  
  20. RULE
  21.  
  22. <<  Ham (the Hamming function) returns an infinite list of numbers
  23.     having two, three and five as only prime factors by recursively
  24.     mapping the functions (*I 2), (*I 3) and (*I 5) over the list of
  25.     Hamming numbers found sofar and merging these lists into one.   
  26. >>
  27. ::  Ham -> [INT];
  28.     Ham -> y: [1 | Merge (Merge (Map (* 2) y) (Map (* 3) y)) (Map (* 5) y)];
  29.  
  30.  
  31. <<  Merge merges two sorted lists of integers into one. Elements that occur
  32.     more than once will be removed (every element should occur only once in
  33.     the final list of Hamming numbers).
  34. >>
  35. ::  Merge [INT]     [INT]   -> [INT];
  36.     Merge []        []      -> [];
  37.     Merge f         []      -> f;
  38.     Merge []        f       -> f;
  39.     Merge f:[a|b]   g:[c|d] -> [a | Merge b g], IF < a c
  40.                             -> Merge f d      , IF = a c
  41.                             -> [c | Merge f d];
  42.  
  43.  
  44. ==  The well-known Map function:
  45.  
  46. ::  Map (=> x y) [x]    -> [y];
  47.     Map f        []     -> [];
  48.     Map f        [a|b]  -> [f a | Map f b];
  49.  
  50.  
  51. ==  Take takes the first n elements of a (possibly infinite) list.
  52.     
  53. ::  Take INT [x] -> [x];
  54.     Take 0 list  -> [];
  55.     Take n [h|t] -> [h | Take (-- n) t];
  56.     Take n []    -> [];
  57.     
  58.  
  59. <<  The Start rule: take the first NrElements numbers from the
  60.     infinite list returned by the Hamming function (Ham).
  61. >>
  62. ::  Start -> [INT];
  63.     Start -> Take NrElements Ham;
  64.